package com.da.javatest.algorithm;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] array = new int[] {8, 10, 2, 3, 6, 1, 5};
        //int[] array = new int[] {1, 2, 3, 4, 5, 6, 7, 8};
        //QuickSort.sort2(array, 0, array.length - 1);
        QuickSort.sort(array);
        System.out.println(Arrays.toString(array));
    }

    // 快速排序，data是数组
    public static void sort(int[] data) {
        quickSortInternally(data, 0, data.length - 1);
    }

    // 快速排序递归函数，start,end为下标
    private static void quickSortInternally(int[] data, int start, int end) {
        if (start >= end) { return; }

        int index = partition2(data, start, end); // 获取分区点
        quickSortInternally(data, start, index - 1);
        quickSortInternally(data, index + 1, end);
    }

    private static int partition(int[] data, int start, int end) {
        int pivot = data[end];
        int index = start - 1;
        for (int j = start; j < end; ++j) {
            if (data[j] < pivot) {
                index++;
                swap(data, index, j);
            }
        }
        // 交换分界点和比较值
        swap(data, ++index, end);

        System.out.println("index = " + index);
        return index;
    }

    private static int partition2(int[] data, int start, int end) {
        int index = start + (int)(Math.random() * (end - start + 1));
        swap(data, index, end);
        int pivot = data[end];
        index = start - 1;
        for (int j = start; j < end; ++j) {
            if (data[j] < pivot) {
                index++;
                swap(data, index, j);
            }
        }
        // 交换分界点和比较值
        swap(data, ++index, end);

        System.out.println("index = " + index);
        return index;
    }

    private static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void sort2(int[] data, int start, int end) {
        if (data == null || start >= end) { return; }
        int i = start, j = end;
        int pivotKey = data[start];
        while (i < j) {
            while (i < j && data[j] >= pivotKey) {
                j--;
            }
            if (i < j) {
                data[i++] = data[j];
            }
            while (i < j && data[i] <= pivotKey) {
                i++;
            }
            if (i < j) {
                data[j--] = data[i];
            }
        }
        data[i] = pivotKey;
        sort2(data, start, i - 1);
        sort2(data, i + 1, end);
    }
}